package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.*;

/**
 * @author tzp
 * @since 2020/9/7
 */
public class LC590_1 implements TreeProblem {
    public static void main(String[] args) {

        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node3 = new Node(3, Arrays.asList(node5, node6));
        Node node1 = new Node(1, Arrays.asList(node3, node2, node4));
        List<Integer> postorder = new LC590_1.Solution().postorder(node1);
        System.out.println(postorder);
    }

    // Definition for a Node.
    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }


    static class Solution {
        public List<Integer> postorder(Node root) {
            Deque<Integer> result = new ArrayDeque<>();
            Deque<Node> queue = new ArrayDeque<>();
            if (root != null) {
                queue.add(root);
                while (queue.size() > 0) {
                    Node node = queue.pop();
                    result.addFirst(node.val);
                    if (node.children != null && node.children.size() > 0) {
                        for (int i = 0; i < node.children.size(); i++) {
                            queue.push(node.children.get(i));
                        }
                    }

                }
            }
            return new ArrayList<>(result);
        }
    }
}
